package A爆炸集;

import com.alibaba.fastjson.JSON;

import java.util.*;

public class No149直线上最多的点数_集合类题 {

    /**
     * 给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。
     * 示例 1:
     * 输入: [[1,1],[2,2],[3,3]]
     * 输出: 3
     * 解释:
     * ^
     * |
     * |        o
     * |     o
     * |  o  
     * +------------->
     * 0  1  2  3  4
     * 示例 2:
     * 输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
     * 输出: 4
     * 解释:
     * ^
     * |
     * |  o
     * |     o        o
     * |        o
     * |  o        o
     * +------------------->
     * 0  1  2  3  4  5  6
     */

    public int maxPoints(int[][] points) {

        if(points.length==0)
            return 0;

        int count=0;

        for(int i=0;i<points.length;i++){
            Map<Double,Integer> map=new HashMap<>();
            int op=0;
            int max=0;
            for(int j=0;j<points.length;j++){
                if(i!=j){
                    //先判断是否重合!
                    if(Arrays.equals(points[j], points[i])) {
                        op++;
                        continue;
                    }
                    Double k=getK(points[i],points[j]);
                    map.put(k,map.getOrDefault(k,0)+1);
                }
            }
            for (Integer value : map.values()) {
                max=Math.max(max,value);
            }
            count=Math.max(count,max+op);
        }

        return count+1;//算上自己
    }

    public int maxPointsTest(int[][] points) {

        int count=0;

        for(int i=0;i<points.length;i++){
//            Map<Double,Integer> map=new HashMap<>();
            Map<Double, List<int[][]>> map=new HashMap<>();
            for(int j=0;j<points.length;j++){
                if(i!=j){
                    double k=getK(points[i],points[j]);
                    List<int[][]> ints = map.get(k);
                    if(ints==null){
                        ints=new ArrayList<>();
                        int[][] arr=new int[][]{points[i],points[j]};
                        ints.add(arr);
                        map.put(k,ints);
                    }else{
                        int[][] arr=new int[][]{points[i],points[j]};
                        ints.add(arr);
                        //不用管
                    }
                }
            }
            for(double d:map.keySet()){
                System.out.println(JSON.toJSONString(map.get(d)));
                count=Math.max(count,map.get(d).size());
            }
        }

        return count+1;//算上自己
    }

    //求两点之间的斜率: (y1-y2)/(x1-x2)
    private Double getK(int[] i,int[] j){
        double result;
        double x1=i[0];
        double y1=i[1];
        double x2=j[0];
        double y2=j[1];

//        if(x1==x2&&y1==y2)
//            return 1D;

        if(x1-x2==0){
            //在一条y上
            return null;
        }
        result=(y1-y2)/(x1-x2);
        return result;
    }



    public int maxPointsGood(int[][] points) {
        if (points.length < 3) {
            return points.length;
        }
        int res = 0;
        //遍历每个点
        for (int i = 0; i < points.length; i++) {
            int duplicate = 0;
            int max = 0;//保存经过当前点的直线中，最多的点
            HashMap<String, Integer> map = new HashMap<>();
            for (int j = i + 1; j < points.length; j++) {
                //求出分子分母
                int x = points[j][0] - points[i][0];
                int y = points[j][1] - points[i][1];
                if (x == 0 && y == 0) {
                    duplicate++;
                    continue;

                }
                //进行约分
                int gcd = gcd(x, y);
                x = x / gcd;
                y = y / gcd;
                String key = x + "@" + y;
                map.put(key, map.getOrDefault(key, 0) + 1);
                max = Math.max(max, map.get(key));
            }
            //1 代表当前考虑的点，duplicate 代表和当前的点重复的点
            res = Math.max(res, max + duplicate + 1);
        }
        return res;
    }

    //精髓,下面有
    private static int gcd(int a, int b) {
        while (b != 0) {//不等于0有两种情况,a>b或者
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }

    private static int myGcd(int a, int b) {

        //保证a大,b小
//        if(a<b) {
//            INT TEMP=A;
//            A = B;
//            B = TEMP;
//        }
        /**
         * 辗转相除法
         * 1.大的对小的求余
         * 2.小的对余数再求余
         * 3.知道余数等于0为止
         */
        while (b != 0) {
            int yu= a%b;//就算小除大,这里得出是小,经过下面的倒置,还是会反过来,继续得以进行
            a=b;//因为是a%b,所以将a变成小的
            b=yu;
        }
        return a;
    }

    public static void main(String[] args) {
        No149直线上最多的点数_集合类题 n=new No149直线上最多的点数_集合类题();
        int[][] arr=new int[][]{{1,1},{2,2},{3,3}};
        int[][] arr2=new int[][]{{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}};
        int[][] arr3=new int[][]{{0,0},{1,1},{1,-1}};
        int[][] arr4=new int[][]{{1,1},{1,1},{2,2},{2,2}};
        int[][] arr5=new int[][]{{3,10},{0,2},{0,2},{3,10}};
        int[][] arr6=new int[][]{{0,0},{0,0},{1,1},{0,0}};
//        int i = n.maxPoints(arr6);
//        System.out.println(i);

//        int ii=gcd(36,99);
//        System.out.println(ii);

        int ii=myGcd(36,99);
        System.out.println(ii);

    }
}
